package ali;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/two-sum/
 * @author wxh
 */
public class Solution_1 {

	/**
	 * 解法一：暴力遍历，时间复杂度在 O(n2)
	 */
	public int[] twoSum(int[] nums, int target) {
		int [] result = new int[2];
		for (int i = 0; i < nums.length; i++) {
			int a1 = nums[i];
			for (int j = i+1; j < nums.length; j++) {
				int a2 = nums[j];
				if (a2 + a1 == target) {
					result[0] = i;
					result[1] = j;
					return result;
				}
			}
		}
		return null;
	}

	/**
	 * 解法二：利用哈希容器 map 降低时间复杂度
	 */
	public int[] twoSum2(int[] nums, int target) {
		Map<Integer, Integer> hashMap = new HashMap(nums.length);
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			// 如果存在则找到了两个值
			if (hashMap.get(num) != null) {
				return new int[] {hashMap.get(num), i};
			}
			// 如果hashMap不存在，则将当前的 (target - nums[i] , i) 存入 map 中
			hashMap.put(target - num, i);
		}
		return null;
	}


}